package Lee_code;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author blh
 * @date 2024年07月01日 19:58
 */
public class Lee_662_71 {
    public int widthOfBinaryTree(TreeNode root) {
        // 使用层序遍历, 使用val标记位置
        root.val = 0;
        int maxWidth = 0;
        TreeNode temp = root;
        traceTree(temp, 1);
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        // 对tree进行层序遍历

        while (!deque.isEmpty()) {
            int size = deque.size();
            maxWidth = Math.max(maxWidth, deque.getLast().val - deque.getFirst().val);

            for (int i = 0; i < size; i++) {
                TreeNode cur = deque.poll();
                System.out.println(cur.val);
                if (cur.left != null) {
                    deque.add(cur.left);
                }
                if (cur.right != null) {
                    deque.add(cur.right);
                }
            }
            System.out.println();

        }
        return maxWidth;
    }

    private void traceTree(TreeNode root, int i) {
        if (root == null) {
            return;
        }
        root.val = i;
        traceTree(root.left, 2 * i);
        traceTree(root.right, 2 * i + 1);
    }
}
